﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<time.h>
#include<string>

using namespace std;

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


// hoare
// [left, right]
void hoare(int* arr,int left,int right)
{
	if (left >= right)
		return;
	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{//先找end再找begin，顺序不能反
		//右边找小于arr[keyi]的数
		while (begin < end && arr[end] >= arr[keyi])
		{
			--end;
		}
		//左边找大于arr[keyi]的数
		while (begin < end && arr[begin] <= arr[keyi])
		{
			++begin;
		}
		Swap(&arr[begin], &arr[end]);
	}
	//相遇位置的值一定比arr[keyi]小
	Swap(&arr[keyi], &arr[begin]);
	keyi = begin;
	//划分区间，递归
	//[left,keyi - 1] keyi [keyi + 1,right]
	hoare(arr, left, keyi - 1);
	hoare(arr, keyi + 1, right);
}



void Lomuto(int* arr, int left,int right)
{
	if (left >= right) return;

	int keyi = rand() % (right - left + 1) + left;
	Swap(&arr[keyi], &arr[left]);
	keyi = left;

	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
			Swap(&arr[prev], &arr[cur]);
		cur++;
	}
	Swap(&arr[keyi], &arr[prev]);
	keyi = prev;
	Lomuto(arr, left, keyi - 1);
	Lomuto(arr, keyi + 1, right);
}

int GetKey(int* arr, int left, int right)
{
	int i = rand();
	return arr[left + i % (right - left + 1)];
}
void ThreeWay(int* arr, int left, int right)
{
	if (left >= right) return;

	int key = GetKey(arr, left, right);
	int begin = left - 1, end = right + 1, cur = left;
	while (cur < end) {
		if (arr[cur] < key) Swap(&arr[++begin], &arr[cur++]);
		else if (arr[cur] > key) Swap(&arr[--end], &arr[cur]);
		else cur++;
	}
	Swap(&arr[begin + 1], &key); // 将基准值放到正确的位置

	ThreeWay(arr, left, begin); // 对小于基准值的子数组递归
	ThreeWay(arr, end, right); // 对大于基准值的子数组递归
}

void test()
{
	//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };
	//PrintArray(a0, sizeof(a0) / sizeof(int));
	//
	//srand(time(NULL));
	//hoare(a0, 0, sizeof(a0) / sizeof(int) - 1);
	//Lomuto(a0, 0, sizeof(a0) / sizeof(int) - 1);
	//ThreeWay(a0, 0, sizeof(a0) / sizeof(int) - 1);
	//PrintArray(a0, sizeof(a0) / sizeof(int));

	int a1[] = { 6,1,7,6,6,6,4,9 };
	int a2[] = { 3,2,3,3,3,3,2,3 };
	int a3[] = { 2,2,2,2,2,2,2,2 };
	srand(time(NULL));
	//hoare(a1, 0, sizeof(a1) / sizeof(int) - 1);
	//PrintArray(a1, sizeof(a1) / sizeof(int));

	//Lomuto(a1, 0, sizeof(a1) / sizeof(int) - 1);
	//PrintArray(a1, sizeof(a1) / sizeof(int));

	//ThreeWay(a1, 0, sizeof(a1) / sizeof(int) - 1);
	//PrintArray(a1, sizeof(a1) / sizeof(int));

	//hoare(a2, 0, sizeof(a2) / sizeof(int) - 1);
	//PrintArray(a2, sizeof(a2) / sizeof(int));

	//Lomuto(a2, 0, sizeof(a2) / sizeof(int) - 1);
	//PrintArray(a2, sizeof(a2) / sizeof(int));

	//ThreeWay(a2, 0, sizeof(a2) / sizeof(int) - 1);
	//PrintArray(a2, sizeof(a2) / sizeof(int));


	hoare(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));

	Lomuto(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));

	ThreeWay(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));
}

void Insertsort(int* arr, int n)
{
	//// [0,end]部分是有序的，将end+1位置的值与end位置值比较
	//for (int i = 1; i < n; i++)
	//{ // 我用的是从0开始，你也可以按别人的从1开始
	//	int end = i - 1;
	//	int tmp = arr[end + 1];
	//	while (end >= 0 && tmp < arr[end])
	//	{
	//		arr[end + 1] = arr[end];
	//		--end;
	//	}
	//	arr[end + 1] = tmp; // 这步才是核心---插入
	//}

	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = arr[i];
		// 将tmp插⼊到[0,end]区间中，保持有序
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
// 向下调整算法(建大堆)
void adjustdown(int* a,int n,int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if ((child + 1 < n) && a[child] < a[child + 1]) ++child;
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else break;
	}
}

void Heapsort(int* arr,int n)
{
	// 建堆,从最后一个根节点开始堆排
	for (int parent = (n - 2) / 2; parent >= 0; parent--)
	{
		adjustdown(arr, n, parent);
	}

	int end = n - 1;
	while (end > 0)
	{
		swap(arr[end], arr[0]);// 最大的数交换到最后为止
		adjustdown(arr, end, 0); // 选出次大的数,传入的parent是0,
		end--; // 将end位置的数锁定在数组
	}
}

void Introsort(int* a, int left, int right, int depth, int defaultdepth)
{
	if (left >= right) return;
	
	int n = right - left + 1;
	// 数组长度小于16，用插入方便
	if (n < 16)
	{	// 注意这里要+left，坑死我了！
		Insertsort(a +left, n); 
		return;
	}
	// 递归深度超过二倍数组长度的对数时，用堆排
	if (depth > defaultdepth)
	{
		Heapsort(a + left, n); 
		return;
	}
	
	// 这两种多不是就用lomuto(前后指针)
	depth++;

	int keyi = rand() % (right - left + 1) + left;
	swap(a[keyi], a[left]);
	keyi = left;

	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			swap(a[prev], a[cur]);
		cur++;
	}
	swap(a[keyi], a[prev]);
	keyi = prev;

	Introsort(a, left, keyi-1,depth,defaultdepth);
	Introsort(a, keyi+1, right, depth, defaultdepth);

}

void QuickSort(int* a, int left, int right)
{
	int logn = 0;
	int N = right - left + 1;
	for (int i = 1; i < N; i *= 2)
	{	// 这里计算的logn就是defaultdepth，
		//introsort算法要求深度depth不超过为2倍排序元素数量的对数值
		logn++;
	}
	Introsort(a, left, right, 0, logn*2);
}

int main()
{
	int a0[] = { 6,1,2,7,9,3,4,5,10,4,8,11,44,55,15,66 };
	PrintArray(a0, sizeof(a0) / sizeof(int));
	srand(time(0));
	QuickSort(a0,0, sizeof(a0) / sizeof(int)-1);
	//Insertsort(a0, sizeof(a0) / sizeof(int));
	//Heapsort(a0, sizeof(a0) / sizeof(int));
	PrintArray(a0, sizeof(a0) / sizeof(int));

	//test();
	return 0;
}

